Search for: All records

Abstract We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters. 

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions $L,R$with $N_L,N_R$qubits, respectively, coupled only through an intermediate region $C$with $N_C$qubits, for any $\delta >0$we show a lower bound of $\mathrm{\Omega }(N_R^{1-\delta }/\sqrt{N_L}{N}_C)$on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between $L$and $C,R$that can be generated in time $t$by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from $O\left(N_{L}t\right)$to $O\left(\sqrt{N_L}t\right)$. As a special case, when applied to the star graph (i.e., one vertex connected to $N$leaves), we obtain an $\mathrm{\Omega }\left(\sqrt{N^{1-\delta }}\right)$lower bound on the routing time and on the time to prepare $N/2$Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time $\mathrm{\Theta }\left(\sqrt{N}\right)$using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time $\mathrm{\Theta }\left(N\right)$. 

Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement. 

Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on verification of an analog quantum simulation, in which the verifier need only run an $O\left({\lambda }^2\right)$-time classical computation, and the prover need only prepare $O\left(1\right)$samples of a history state and perform $O\left({\lambda }^2\right)$single-qubit measurements, for a security parameter $\lambda$. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations. Published by the American Physical Society2025 

Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes that affects code performance and ease of physical realization. For device architectures restricted to two-dimensional (2D) local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive overhead. In this work, we present an error-correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of bivariate-bicycle qLDPC codes and show that they are well suited for a parallel syndrome-measurement scheme using fast routing with local operations and classical communication (LOCC). Through circuit-level simulations, we find that in some parameter regimes, bivariate-bicycle codes implemented with this protocol have logical error rates comparable to the surface code while using fewer physical qubits. Published by the American Physical Society2025 

We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation—showing an $O\left(\sqrt{NlogN}\right)$upper bound on the separation in routing time for any interaction graph—and give tighter bounds for some common classes of graphs. Published by the American Physical Society2024 

Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of ann-dimensional convex body within multiplicative error ε usingÕ(n³+ n^2.5/ε) queries to a membership oracle andÕ(n⁵+n^4.5/ε)additional arithmetic operations. For comparison, the best known classical algorithm usesÕ(n^3.5+n³/ε²)queries andÕ(n^5.5+n⁵/ε²)additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of “Chebyshev cooling,” where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requiresΩ (√ n+1/ε)quantum membership queries, which rules out the possibility of exponential quantum speedup innand shows optimality of our algorithm in 1/ε up to poly-logarithmic factors.